Например, Бобцов

Планирование распределенных вычислений в недетерминированных системах 

Аннотация:

Введение. Планирование вычислений занимает важное место в процессе проектирования распределенных систем обработки информации и управления. Эффективные алгоритмы планирования позволяют находить технические решения, адекватные существующим ограничениям. Это становится особенно актуально для вычислителей, размещенных на автономных носителях, таких как беспилотные летательные аппараты, необитаемые подводные аппараты и другие подвижные объекты. В работе предложены и исследованы алгоритмы планирования заданий для распределенной вычислительной недетерминированной системы в случае, когда время выполнения заданий известно неточно и задано в виде временных интервалов. Метод. Решение поставленной задачи достигается путем сведения ее к известной задаче flow shop планирования с последующим применением формализма разрешимых классов распределенных вычислительных систем. Основные результаты. Предложены два алгоритма планирования заданий для недетерминированной распределенной вычислительной системы. Алгоритмы допускают отсутствие изоморфизмов между графами заданий и графом межпроцессорных связей. В этом случае невозможно применение известных алгоритмов flow shop планирования. Алгоритмы предполагают предварительное приведение рассматриваемой системы к требуемому виду и базируются на положениях интервального анализа и понятии разрешимого класса распределенных вычислительных систем. Критерием оптимальности предложенных алгоритмов служит минимум среднего времени пребывания задания в системе. Дополнительно для второго алгоритма используется критерий минимума максимального отклонения от заданных директивных сроков. Для введенных разрешимых классов систем для обоих критериев сформулированы оптимальные алгоритмы планирования полиномиальной сложности. Обсуждение. Предложенные решения могут быть применены при планировании вычислений в распределенных вычислительных системах при неточно известных длительностях решаемых задач, в частности, при планировании экономических процессов.

Ключевые слова:

Постоянный URL

Статьи в номере

Содержание © 1993–2025 Университет ИТМО
Разработка © 2015 Университет ИТМО